package junior.Recursion递推;

/**
 递推算法
*/
public class MonkeyClimbMountains {
    public static void main(String[] args) {
        MonkeyClimbMountains mcm = new MonkeyClimbMountains();
        long startTime = System.currentTimeMillis();
        int sums = mcm.fun(50);
        long endTime = System.currentTimeMillis();
        System.out.println(sums);
        System.out.println("执行时间："+(endTime-startTime)+"ms");
    }

/**
 递推算法求解猴子爬山
 */
    public int fun(int steps){
        int[] step = new int[1000];
        step[1]=1;
        step[2]=1;
        step[3]=2;
        for (int i = 4; i <= steps; i++) {
            step[i] = step[i-1]+step[i-3];
        }
        return step[steps];
    }
}
